package org.review.algorithm.search;

import org.review.algorithm.sort.QuickSort;
import org.review.algorithm.sort.Sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Search {
    static int count = 0;

    /**
     * 二分查找
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] ints = new int[]{0,1, 2, 3, 4, 5, 6};
        //int[] ints = Sort.initArray(10);
        // Sort.showTime();
        QuickSort.sort3(ints, 0, ints.length - 1);
        Sort.showArray(ints);

        Sort.showTime();
        System.out.println(FibonacciSearch12(ints, 0));
        Sort.showTime();
    }

    public static int linearSearch(int[] arr, int e) {
        for (int i = 0; i < arr.length; i++) {

            if (arr[i] == e) return i;
        }
        return -1;
    }

    /**
     * @param arr
     * @param e
     * @param left
     * @param right
     * @return
     */
    public static int binarySearch(int[] arr, int e, int left, int right) {
        if (left > right) {
            return -1;
        }
        System.out.println("查找次数" + count++);
        int mid = (left + right) / 2;

        if (arr[mid] > e) {
            return binarySearch(arr, e, left, mid - 1);
        } else if (arr[mid] < e) {
            return binarySearch(arr, e, mid + 1, right);
        } else {
            return mid;

        }
    }


    public static int binaraySearchNoRecursion(int[] arr, int e, int left, int right) {
        if (left > right) return -1;
        int l = left, r = right, mid = (left + right) / 2;

        while (l < r) {
            System.out.println("查找次数" + count++);
            mid = (l + r) / 2;
            if (arr[mid] > e) {
                r = mid - 1;
            } else if (arr[mid] < e) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 查找所有符合条件的值并返回
     * 分析：因为实在有序队列中查找，当查找到以后，一定是和它的旁边一个
     */
    public static List binarySearch2(int[] arr, int e, int left, int right) {
        if (left > right) {
            return new ArrayList<Integer>();
        }
        System.out.println("查找次数" + count++);
        int mid = (left + right) / 2;

        if (arr[mid] > e) {
            return binarySearch2(arr, e, left, mid - 1);
        } else if (arr[mid] < e) {
            return binarySearch2(arr, e, mid + 1, right);
        } else {
            ArrayList<Integer> vars = new ArrayList<>();
            //TODO 2024/11/25:当找到已有，需要向左右扫描
            int temp = mid - 1;
            while (temp >= 0 && arr[temp] == e) {
                vars.add(temp);
                temp--;
            }

            vars.add(mid);

            //TODO 2024/11/25:当找到已有，需要向左右扫描
            temp = mid + 1;
            while (temp <= right && arr[temp] == e) {

                vars.add(temp);
                temp++;
            }
            return vars;

        }
    }


    public static List chazhiSearch(int[] arr, int e, int left, int right) {
        if (left > right || e < arr[left] || e > arr[right]) {
            return new ArrayList<Integer>();
        }
        System.out.println("查找次数" + count++);
        //TODO 2024/12/2:这个插值可能越界
        int mid = left + (right - left) * (e - arr[left]) / (arr[right] - arr[left]);

        if (arr[mid] > e) {
            return binarySearch2(arr, e, left, mid - 1);
        } else if (arr[mid] < e) {
            return binarySearch2(arr, e, mid + 1, right);
        } else {
            ArrayList<Integer> vars = new ArrayList<>();
            //TODO 2024/11/25:当找到已有，需要向左右扫描
            int temp = mid - 1;
            while (temp >= 0 && arr[temp] == e) {
                vars.add(temp);
                temp--;
            }

            vars.add(mid);

            //TODO 2024/11/25:当找到已有，需要向左右扫描
            temp = mid + 1;
            while (temp <= right && arr[temp] == e) {

                vars.add(temp);
                temp++;
            }
            return vars;
        }
    }

    /**
     * 斐波那契查找依赖于 上边的非递归实现二分查找
     * 需要先有一个斐波那契的等差数列 长度与待查找相同
     *
     * @param arr
     * @param e
     * @return
     */
    public static int FibonacciSearch1(int[] arr, int e) {
        int count = 0;
        int n = arr.length;
        int[] fib = fib(n);

        int l = 0, r = n - 1;

        int k = 0;
        int mid = 0;
        while (fib[k] - 1 < n) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr, fib[k]);
        //TODO 2024/12/18:fib[k] 的长度可能是大于或等于n的，所有要将temp 补齐

        for (int i = r + 1; i < temp.length; i++) {
            temp[i] = arr[r];
        }

        while (l < r) {
            mid = l + fib[k - 1] - 1;
            System.out.println(++count);
            if (temp[mid] < e) {
                l = mid + 1;
                k -= 2;
            } else if (temp[mid] > e) {
                r = mid - 1;
                k -= 1;
            } else {
                //TODO 2024/12/18:如果mid>r 时候，temp 所有的元素都是用arr末尾元素补齐的，所以返回末尾元素的下标
                return Math.min(r, mid);
            }
        }

        return -1;
    }

    /**
     * 斐波那契数列
     *
     * @param len
     * @return
     */
    public static int[] fib(int len) {
        if (len <= 0) throw new RuntimeException("长度无效");
        int[] f = new int[len];

        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < len; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 另外一种斐波那契查找， 都是利用斐波那契数列的值
     *
     * @param arr
     * @param e
     * @return
     */
    public static int FibonacciSearch12(int[] arr, int e) {
        int n = arr.length;
        int f1 = 1;
        int f2 = 1;
        int f = f1 + f2;
        while (f < n) {
            f2 = f1;
            f1 = f;
            f = f1 + f2;
        }

        int offset = -1; //TODO 2024/12/23:这里是-1的时候 下边就不需要f2-1， 否则就需要-1，因为斐波那契数列值需要-1，才能表示数组下表

        while (f > 1) {
            int i = Math.min(offset + f2 , n - 1);

            if (arr[i] == e) return i;
            if (arr[i] < e) {//TODO 2024/12/23:大于分割点
                f = f1;
                f1 = f2;
                f2 = f - f1;
                offset = i;
            } else if (arr[i] > e) {
                f = f2;
                f1 = f1 - f2;
                f2 = f - f1;
            }

        }
        //TODO 2024/12/23:f>1 这部分如果不满足，那么会走到这一步
        if (f1 == 1 && arr[offset+1] == e) {
            return offset+1;
        }
        return -1;  // 如果未找到目标元素，返回 -1
    }
}
